package com.mystudy.leetcode.problem.sort.p_148;

/**
 * @program: infoalgorithm
 * @description: 排序链表
 * @author: zhouzhilong
 * @create: 2019-08-02 09:52
 **/

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);
    long startTime = 0L;
    long endTime = 0L;

    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{1, 2, 3, 4});
        ListNode result = sortList(listNode);
        ListNodeUtils.show(result);


    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]", cost);
    }

    public ListNode sortList(ListNode head) {
        ListNode sort = sort(head);
        return sort;
    }

    private ListNode sort(ListNode node){
        if(node == null ||node.next == null){
            return node;
        }
        //归并排序
        ListNode fast = node.next;
        ListNode lazy = node;
        while(fast != null){
          if(fast.next == null || fast.next.next == null){
              fast = null;
          }else{
              fast = fast.next.next;
              lazy = lazy.next;
          }
        }
        //断开链表
        ListNode leftList = node;
        ListNode rightList = lazy.next;
        lazy.next = null;
        ListNode leftResult = sort(leftList);
        ListNode rightResult = sort(rightList);
        ListNode result = null;
        ListNode cur = result;
        while(leftResult!=null && rightResult != null){
            if(leftResult.val<rightResult.val){
                if(result == null){
                    result = leftResult;
                    cur = result;
                }else{
                    cur.next = leftResult;
                    cur = cur.next;
                }
                leftResult = leftResult.next;
            }else{
                if(result == null){
                    result = rightResult;
                    cur =result;
                }else{
                    cur.next = rightResult;
                    cur = cur.next;
                }
                rightResult = rightResult.next;
            }
        }
        while(leftResult!=null){
            cur.next = leftResult;
            cur = cur.next;
            leftResult = leftResult.next;
        }

        while(rightResult!=null){
            cur.next = rightResult;
            cur = cur.next;
            rightResult = rightResult.next;
        }

        return result;
    }


}
